package Algorithm.DynamicPlanning;

// 给定"a-z"字母，有多少种不同的子序列，不算空串
public class Code18_DistinctSubseq {

    public static int distinctSubseq1(String s){
        if (s == null || s.length() == 0){
            return 0;
        }
        char[] str = s.toCharArray();
        int[] count = new int[26];
        int all = 0;
        for (int i = 0; i < str.length; i++) {
            int add = all + 1 - count[str[i] - 'a'];
            count[str[i] - 'a'] += add;
            all += add;
        }
        return all;
    }

    public static void main(String[] args) {
        String s = "aaaab";
        System.out.println(distinctSubseq1(s));
    }
}
